#include <algorithm>
#include <cstdio>

#define int long long

typedef long long ll;
const int N = 50005, BASE = 10000;
int n, m, p, c, cnt, a[N], phi[N];
ll fastpow[2][N][40];
bool over[2][N][40];

struct Node {
  int val, cnt;
} tr[N << 2];

inline void pushup(int x) {
  tr[x].val = tr[x << 1].val + tr[x << 1 | 1].val;
  tr[x].cnt = std::min(tr[x << 1].cnt, tr[x << 1 | 1].cnt);
}

inline int getphi(int x) {
  int res = x;
  for (int i = 2; i * i <= x; ++i) {
    if (x % i == 0) {
      res = res / i * (i - 1);
      while (x % i == 0) x /= i;
    }
  }
  if (x != 1) res = res / x * (x - 1);
  return res;
}

void build(int, int, int);

inline void init() {
  int tmp = p;
  phi[0] = p;
  while (tmp != 1) tmp = getphi(tmp), phi[++cnt] = tmp;
  phi[++cnt] = 1;
  for (int i = 0; i <= cnt; ++i) {
    fastpow[0][0][i] = 1;
    for (int j = 1; j <= BASE; ++j) {
      fastpow[0][j][i] = fastpow[0][j - 1][i] * c;
      if (fastpow[0][j][i] >= phi[i]) fastpow[0][j][i] %= phi[i], over[0][j][i] = 1;
      over[0][j][i] |= over[0][j - 1][i];
    }
  }
  for (int i = 0; i <= cnt; ++i) {
    fastpow[1][0][i] = 1;
    over[1][1][i] = over[0][BASE][i];
    for (int j = 1; j <= BASE; ++j) {
      fastpow[1][j][i] = fastpow[1][j - 1][i] * fastpow[0][BASE][i];
      if (fastpow[1][j][i] >= phi[i]) fastpow[1][j][i] %= phi[i], over[1][j][i] = 1;
      over[1][j][i] |= over[1][j - 1][i];
    }
  }
  build(1, 1, n);
}

void build(int x, int l, int r) {
  if (l == r) return tr[x].val = a[l] % p, void();
  int mid = (l + r) >> 1;
  build(x << 1, l, mid);
  build(x << 1 | 1, mid + 1, r);
  pushup(x);
}

bool f;
inline int qpow(int k, int mod) {
  f |= over[0][k % BASE][mod] | over[1][k / BASE][mod];
  int res = fastpow[0][k % BASE][mod] * fastpow[1][k / BASE][mod];
  if (res >= phi[mod]) f = true, res %= phi[mod];
  return res;
}

inline int solve(int base, int tim) {
  if (base > phi[tim]) base = base % phi[tim] + phi[tim];
  for (int i = tim; i; --i) {
    f = false;
    base = qpow(base, i - 1);
    if (f) base += phi[i - 1], f = false;
  }
  return base % p;
}

void modify(int x, int l, int r, int L, int R) {
  if (tr[x].cnt >= cnt) return;
  if (l == r) { return ++tr[x].cnt, tr[x].val = solve(a[l], tr[x].cnt), void(); }
  int mid = (l + r) >> 1;
  if (L <= mid) modify(x << 1, l, mid, L, R);
  if (mid < R) modify(x << 1 | 1, mid + 1, r, L, R);
  pushup(x);
}

int query(int x, int l, int r, int L, int R) {
  if (L <= l && r <= R) return tr[x].val;
  int mid = (l + r) >> 1;
  int res = 0;
  if (L <= mid) res += query(x << 1, l, mid, L, R);
  res %= p;
  if (mid < R) res += query(x << 1 | 1, mid + 1, r, L, R);
  return res % p;
}

signed main() {
#ifndef ONLINE_JUDGE
#ifdef LOCAL
  freopen("testdata.in", "r", stdin);
  freopen("testdata.out", "w", stdout);
#else
  freopen("P3747 [六省联考2017]相逢是问候.in", "r", stdin);
  freopen("P3747 [六省联考2017]相逢是问候.out", "w", stdout);
#endif
#endif

  scanf("%lld%lld%lld%lld", &n, &m, &p, &c);
  for (int i = 1; i <= n; ++i) { scanf("%lld", &a[i]); }
  init();
  for (int l, r, opt; m; m--) {
    scanf("%lld%lld%lld", &opt, &l, &r);
    if (opt) {
      printf("%lld\n", query(1, 1, n, l, r));
    } else {
      modify(1, 1, n, l, r);
    }
  }
  return 0;
}